package com.axzh.interview.base;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class GraphAlgorithm {

	public static void main(String[] args) {
		Graph graph = new Graph(8);
		String[] vertices = {"A","B","C","D","E","F","G","H"};
		graph.addVertex(vertices);
		graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(3, 7);
        graph.addEdge(4, 7);
        graph.addEdge(2, 5);
        graph.addEdge(2, 6);
        graph.addEdge(5, 6);
        graph.addEdge(1, 0);
        graph.addEdge(2, 0);
        graph.addEdge(3, 1);
        graph.addEdge(4, 1);
        graph.addEdge(7, 3);
        graph.addEdge(7, 4);
        graph.addEdge(4, 2);
        graph.addEdge(5, 2);
        graph.addEdge(6, 5);
        
        graph.BFS();
        System.out.println();
        graph.DFS();
	}

}

class Graph {
	
	private ArrayList<Object> vertex;
	private int[][] edges;
	//private int numOfEdges = 0;//
	private boolean[] visited;
	
	public Graph(int n) {
		vertex = new ArrayList<>(n);
		edges = new int[n][n];
		visited = new boolean[n];
	}
	
	public void addVertex(Object[] vex) {
		for(int i=0;i<vex.length;i++) {
			vertex.add(i, vex[i]);
		}
	}
	
	public void addEdge(int v1,int v2) {
		edges[v1][v2]=1;
		//numOfEdges++;
	}
	
	private int getFirstAdjVex(int v1) {
		for(int j=0;j<vertex.size();j++) {
			if(edges[v1][j]>0) {
				return j;
			}
		}
		return -1;
	}
	
	private int getNextAdjVex(int v1, int v2) {
		for(int j=v2+1;j<vertex.size();j++) {
			if(edges[v1][j]>0) {
				return j;
			}
		}
		return -1;
	}
	
	public void BFS() {
		for(int i=0;i<visited.length;i++) {
			visited[i]=false;
		}
		for(int i=0;i<vertex.size();i++) {
			if(!visited[i]) {
				BFS(i);
			}
		}
	}
	
	private void BFS(int i) {
		Queue<Integer> queue = new LinkedList<Integer>();
		System.out.print(vertex.get(i)+" ");
		visited[i]=true;
		queue.add(i);
		while(!queue.isEmpty()) {
			int v1 = queue.remove();
			int v2 = getFirstAdjVex(v1);
			while(v2!=-1) {
				if(!visited[v2]) {
					System.out.print(vertex.get(v2)+" ");
					visited[v2]=true;
					queue.add(v2);
				}
				v2 = getNextAdjVex(v1, v2);
			}
		}
	}
	
	public void DFS() {
		for(int i=0;i<visited.length;i++) {
			visited[i]=false;
		}
		for(int i=0;i<vertex.size();i++) {
			if(!visited[i]) {
				DFS(i);
			}
		}
	}
	
	private void DFS(int i) {
		System.out.print(vertex.get(i)+" ");
		visited[i]=true;
		int v1 = getFirstAdjVex(i);
		while(v1!=-1) {
			if(!visited[v1]) {
				DFS(v1);
			}
			v1 = getNextAdjVex(i, v1);
		}
	}
	
	public void kruskal() {
		int numOfVex = vertex.size();
		//int[] vertics = new int[numOfVex];
		int min = Integer.MAX_VALUE;
		for(int i=0;i<numOfVex;i++) {
			for(int j=i+1;j<numOfVex;j++) {
				if(edges[i][j]>0 && edges[i][j]<min) {
					
				}
			}
		}
	}
	
	public static void prim() {
		
	}
	
}
